package com.nanbei.backyracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassDescription: (回溯算法 leetCode77)  给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/12 14:56
 */
public class Combinations {

    public static void main(String[] args) {
        List<List<Integer>> combine = combine(4, 3);
        System.out.println(combine);
    }

    public static List<List<Integer>> combine(int n, int k) {


        List<List<Integer>> target = new ArrayList<>();
        LinkedList<Integer> stack = new LinkedList<>();
        sf(target, stack, n, 1, k);
        return target;
    }

    private static void sf(List<List<Integer>> target, LinkedList<Integer> stack, int n, int index, int k) {
        // 当栈中的元素数量等于数组长度时，表示找到了一种排列
        if (stack.size() == k) {
            target.add(new ArrayList<>(stack));
            return;
        }

        for (int i = index; i <= n; i++) {
            // 所需要的元素个数  >  还剩余的元素个数
            if (k-stack.size()  > n - i+1 ){
                return;
            }


            // 将该数字加入栈中
            stack.push(i);
            // 递归调用后面的数字
            sf(target,stack,n,i+1,k);
            // 回溯：将该数字移出栈
            stack.pop();


        }

    }
}
